public class Leetcode2397 {

    public static void main(String[] args) {
        System.out.println(maximumRows(new int[][]{
                {0, 0, 0}, {1, 0, 1}, {0, 1, 1}, {0, 0, 1}
        }, 2));
    }

    public static int maximumRows(int[][] matrix, int numSelect) {
        int row = matrix.length;
        int column = matrix[0].length;
        int maxZeroRowNumber = 0;

        int sum = 1 << column;
        for (int i = 0; i < sum; i++) {
            if (Integer.bitCount(i) != numSelect) {
                continue;
            }

            maxZeroRowNumber = Math.max(
                    maxZeroRowNumber,
                    computeZeroRowNumber(matrix, row, column, i)
            );
        }

        return maxZeroRowNumber;
    }

    private static int computeZeroRowNumber(int[][] matrix, int row, int column, int i) {
        int zeroRowNumber = 0;
        for (int rowIndex = 0; rowIndex < row; rowIndex++) {
            boolean flag = true;
            for (int columnIndex = 0; columnIndex < column; columnIndex++) {
                if ((i & 1 << columnIndex) != 0) {
                    continue;
                }
                if (matrix[rowIndex][columnIndex] != 0) {
                    flag = false;
                    break;
                }
            }

            if (flag) {
                zeroRowNumber++;
            }
        }

        return zeroRowNumber;
    }
}
